package org.nowcoder.huawei.other;

import java.util.ArrayList;
import java.util.Comparator;

/**
 * NC37: 合并区间
 */
public class NC37 {

    public class Interval {
        int start;
        int end;

        public Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        //边界条件
        if (intervals.size() <= 1) {
            return intervals;
        }
        ArrayList<Interval> result = new ArrayList<>();

        //按照区间起点排序
        intervals.sort(Comparator.comparingInt(o -> o.start));
        result.add(intervals.get(0));

        for (int i = 1; i < intervals.size(); i++) {
            Interval pre = result.remove(result.size() - 1);
            Interval cur = intervals.get(i);
            if (cur.start <= pre.end) {
                pre.end = Math.max(cur.end, pre.end);
                result.add(pre);
            } else {
                result.add(pre);
                result.add(cur);
            }
        }
        return result;
    }
}
